public class BinarySearchTree {
    public static class Node {
        int key;
        Node left;
        Node right;
        public Node(int key) {
            this.key = key;
        }
    }
    private Node root = null;
    public Node search(int key){
        Node cur = root;
        while(cur!=null){
            if(cur.key == key){
                return cur;
            }
            if(cur.key>key){
                cur = cur.left;
            }
            if(cur.key<key){
                cur = cur.right;
            }
        }
        return cur;
    }
    public boolean insert(int key){
        Node  cur = root;
        Node parent = null;
        while(cur!=null){
            if(cur.key==key){
                return false;
            }
            if(cur.key>key){
                parent = cur;
                cur = cur.left;
            }
            if(cur.key<key){
                parent = cur;
                cur = cur.right;
            }
        }
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }
    public boolean remove(int key){
        Node cur = root;
        Node parent = null;
        while(cur!=null){
            if(cur.key==key){
                break;
            }
            if(cur.key>key){
                parent = cur;
                cur = cur.left;
            }
            if(cur.key<key){
                parent = cur;
                cur = cur.right;
            }
        }
        if(cur==null){
            return false;
        }

        //左右孩子均为空
        if(cur==root){
            root=null;
            return true;
        }else {
            if(cur == parent.left){
                parent.left = null;
            }else {
                parent.right = null;
            }
        }

        //左孩子为空，右孩子不为空
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
        }

        //左孩子不为空，有孩子为空
        if(cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if(cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }

        //左右孩子均不为空
        if(cur.left != null&&cur.right != null){
            Node target = cur.right;
            Node targetparent = cur;
            if(cur == root){
                cur = cur.right;
            }else {
                while(target != null){
                    targetparent = target;
                    target = target.left;
                }
                cur.key = target.key;
                if(targetparent.left == target){
                        targetparent.left = target.right;
                }else {
                    targetparent.right = target.right;
                }
            }
        }
        return true;
    }
}
